class Node:
    def __init__(self):
        self.data = None
        self.next = None
        self.prev = None


class Link:
    def __init__(self, data=()):
        self.head = Node()
        self.tail = self.head
        self.length = 0
        for d in data:
            self.append(d)

    def __find_node_by(self, pos):
        nodeptr = self.head
        while pos:
            nodeptr = nodeptr.next
            pos -= 1
        return nodeptr

    def append(self, data):
        node = Node()
        node.data = data
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        self.length += 1

    def pop(self, i=-1):
        if len(self) <= 0:
            raise Exception("The list is empty")

        if i == -1:
            node = self.tail
            self.tail = node.prev
            self.tail.next = None
            self.length -= 1
            return node.data
        else:
            node = self.__find_node_by(i)
            cur_node = node.next
            third_node = node.next.next
            if third_node is not None:
                third_node.prev = node
            node.next = third_node
            self.length -= 1
            return cur_node.data

    def insert(self, i, data):
        assert i <= len(self) - 1
        nodeptr = self.head
        while i:
            nodeptr = nodeptr.next
            i -= 1

        third_node = nodeptr.next
        node = Node()
        node.data = data

        node.next = third_node
        third_node.prev = node

        nodeptr.next = node
        node.prev = nodeptr
        self.length += 1

    def remove(self, i):
        assert i <= len(self) - 1
        nodeptr = self.__find_node_by(i)
        third_node = nodeptr.next.next
        nodeptr.next = third_node
        third_node.prev = nodeptr
        self.length -= 1

    def __len__(self):
        return self.length

    def __iter__(self):
        return LinkIterator(self)

    def __setitem__(self, key, value):
        raise NotImplementedError

    def __getitem__(self, item):
        assert item <= len(self) - 1
        nodeptr = self.head.next
        while item:
            nodeptr = nodeptr.next
            item -= 1

        return nodeptr.data

    def __contains__(self, item):
        for d in self:
            if d == item:
                return True
        return False
    def __add__(self, other):
        for i in other:
            self.append(i)
        return self
    def __str__(self):
        return str([i for i in self])


class LinkIterator:
    def __init__(self, link):
        self._node_ptr = link.head

    def __next__(self):
        self._node_ptr = self._node_ptr.next
        if self._node_ptr is None:
            raise StopIteration
        data = self._node_ptr.data
        return data


list = Link
# x = list()
# x.append(1)
# x.append(2)
# x.append(3)
#
# while x:
#     print(x.pop())

l1 = list((1,2,3))
l2 = list((5,6,7))
l3 = l1 + l2
print(l3)
# print(l1.add(3))
# x[0] = 1
# y = x[0]
#
# for d in x:
#     for y in x:
#         print(y)


# x.insert(1, 8)
# for d in x:
#     print(d)
#
# print("\n")
# x.remove(1)
# for d in x:
#     print(d)

# if 2 in x:
#     print("2 is in list")
#
# print("The 2th is: %d" % x[1])